#include "sort.h"
/*
时间复杂度：O(n²)
空间复杂度：O(1)
*/
void sort(int *arr, int len)
{
    for (int gap = len / 2; gap >= 1; gap = gap / 2)
    {
        for (int i = gap; i < len; i++)
        {
            int cur = arr[i];
            int j;
            for (j = i - gap; j >= 0; j = j - gap)
            {
                if (arr[j] > cur)
                {
                    arr[j + gap] = arr[j];
                }
                else 
                {
                    break;
                }
            }
            arr[j + gap] = cur;
        }
    }
}